1   // Fig. 15.16: treenode.h
2   // Definition of class TreeNode
3   #ifndef TREENODE_H
4   #define TREENODE_H
5   
6   template< class NODETYPE > class Tree;  // forward declaration
7   
8   template< class NODETYPE >
9   class TreeNode {
10     friend class Tree< NODETYPE >;
11  public:
12     TreeNode( const NODETYPE &d )   
13        : leftPtr( 0 ), data( d ), rightPtr( 0 ) { }
14     NODETYPE getData() const { return data; }
15  private:
16     TreeNode< NODETYPE > *leftPtr;  // pointer to left subtree
17     NODETYPE data;
18     TreeNode< NODETYPE > *rightPtr; // pointer to right subtree
19  };
20  
21  #endif
22  
23  
24  // Fig. 15.16: fig15_16.cpp
25  // Definition of template class Tree
26  #ifndef TREE_H
27  #define TREE_H
28  
29  #include <iostream.h>
30  #include <assert.h>
31  #include "treenode.h"
32  
33  template< class NODETYPE >
34  class Tree {
35  public:
36     Tree();
37     void insertNode( const NODETYPE & );
38     void preOrderTraversal() const;
39     void inOrderTraversal() const;
40     void postOrderTraversal() const;
41  private:
42     TreeNode< NODETYPE > *rootPtr;
43  
44     // utility functions
45     void insertNodeHelper( 
46             TreeNode< NODETYPE > **, const NODETYPE & );
47     void preOrderHelper( TreeNode< NODETYPE > * ) const;
48     void inOrderHelper( TreeNode< NODETYPE > * ) const;
49     void postOrderHelper( TreeNode< NODETYPE > * ) const;
50  };
51  
52  template< class NODETYPE >
53  Tree< NODETYPE >::Tree() { rootPtr = 0; }
54  
55  template< class NODETYPE >
56  void Tree< NODETYPE >::insertNode( const NODETYPE &value )
57     { insertNodeHelper( &rootPtr, value ); }
58  
59  // This function receives a pointer to a pointer so the
60  // pointer can be modified.
61  template< class NODETYPE >
62  void Tree< NODETYPE >::insertNodeHelper( 
63          TreeNode< NODETYPE > **ptr, const NODETYPE &value )
64  {
65     if ( *ptr == 0 ) {                   // tree is empty
66        *ptr = new TreeNode< NODETYPE >( value );
67        assert( *ptr != 0 );
68     }
69     else                              // tree is not empty
70        if ( value < ( *ptr )->data )
71           insertNodeHelper( &( ( *ptr )->leftPtr ), value );
72        else
73           if ( value > ( *ptr )->data )
74              insertNodeHelper( &( ( *ptr )->rightPtr ), value );
75           else
76              cout << value << " dup" << endl;
77  }
78  
79  template< class NODETYPE > 
80  void Tree< NODETYPE >::preOrderTraversal() const
81     { preOrderHelper( rootPtr ); }
82  
83  template< class NODETYPE >
84  void Tree< NODETYPE >::preOrderHelper( 
85                            TreeNode< NODETYPE > *ptr ) const
86  {
87     if ( ptr != 0 ) {
88        cout << ptr->data << ' ';
89        preOrderHelper( ptr->leftPtr );
90        preOrderHelper( ptr->rightPtr );
91     }
92  }
93  
94  template< class NODETYPE >
95  void Tree< NODETYPE >::inOrderTraversal() const
96     { inOrderHelper( rootPtr ); }
97  
98  template< class NODETYPE >
99  void Tree< NODETYPE >::inOrderHelper( 
100                           TreeNode< NODETYPE > *ptr ) const
101 {
102    if ( ptr != 0 ) {
103       inOrderHelper( ptr->leftPtr );
104       cout << ptr->data << ' ';
105       inOrderHelper( ptr->rightPtr );
106    }
107 }
108 
109 template< class NODETYPE >
110 void Tree< NODETYPE >::postOrderTraversal() const
111    { postOrderHelper( rootPtr ); }
112 
113 template< class NODETYPE >
114 void Tree< NODETYPE >::postOrderHelper( 
115                           TreeNode< NODETYPE > *ptr ) const
116 {
117    if ( ptr != 0 ) {
118       postOrderHelper( ptr->leftPtr );
119       postOrderHelper( ptr->rightPtr );
120       cout << ptr->data << ' ';
121    }
122 }
123 
124 #endif
125 
126 
127 // Fig. 15.16: fig15_16.cpp
128 // Driver to test class Tree
129 #include <iostream.h>
130 #include <iomanip.h>
131 #include "tree.h"
132 
133 int main()
134 {
135    Tree< int > intTree;
136    int intVal;
137 
138    cout << "Enter 10 integer values:\n";
139    for( int i = 0; i < 10; i++ ) {
140       cin >> intVal;
141       intTree.insertNode( intVal );
142    }
143 
144    cout << "\nPreorder traversal\n";
145    intTree.preOrderTraversal();
146 
147    cout << "\nInorder traversal\n";
148    intTree.inOrderTraversal();
149 
150    cout << "\nPostorder traversal\n";
151    intTree.postOrderTraversal();
152 
153    Tree< double > doubleTree;
154    double doubleVal;
155 
156    cout << "\n\n\nEnter 10 double values:\n"
157         << setiosflags( ios::fixed | ios::showpoint )
158         << setprecision( 1 );
159    for ( i = 0; i < 10; i++ ) {
160       cin >> doubleVal;
161       doubleTree.insertNode( doubleVal );
162    }
163 
164    cout << "\nPreorder traversal\n";
165    doubleTree.preOrderTraversal();
166 
167    cout << "\nInorder traversal\n";
168    doubleTree.inOrderTraversal();
169 
170    cout << "\nPostorder traversal\n";
171    doubleTree.postOrderTraversal();
172 
173    return 0;
174 }